A technique called clustering that classifies patterns based on similarities between patterns is known. The clustering is a technique that is widely applied for fields such as image recognition, speech recognition, spectrum pattern classification, and data mining. In these application fields, patterns may not be always be input such that they can be easily compared. There are many situations in which, for instance, high dimensional patterns may be input, input patterns may be partly missed, and data may contain outliers. Thus, clustering needs to have high robustness against data missing and outliers and also needs to deal with high dimensional patterns.
As described above, one problem as to clustering is noises such as data missing and outliers. To satisfactorily perform clustering, noises are normally removed from input patterns in a pre-process. However, if data as a feature to be compared is partly missed or data contains outliers, it is not easy to remove such noises.
For instance, in fingerprint classification, features with respect to portions to be compared may not be always detected. In such a case, patterns need to be classified in the state in which features are partly missed. In addition, if there is an occlusion in image recognition, an image pattern including a partial image that is not a target to be compared may needs to be used for comparison. In speech recognition, it may be necessary to use a speech pattern, superimposed with a sudden and short-period noise, for comparison.
As one method that can enhance robustness upon clustering for patterns containing noises, there is an approach that uses an ordinal scale. Patent Document 1 describes a method that enhances robustness against changes of illumination intensities and so forth using an ordinal scale. On the other hand, Patent Document 2 discloses a method that deals with outliers by employing a voting method that uses inverse numbers of distances as similarities of the same categories.
As another problem as to clustering, the higher the dimensions of patterns, the lower the recognition accuracies of the patterns. This results from the fact that neighbor determination becomes unstable due to the spherical surface concentration phenomenon in high dimensional space. This situation is known as “the curse of dimensions” (refer to Non-Patent Document 1).
One method to avoid this problem is to reduce the number of dimensions. As techniques for reducing the number of dimensions, although principal component analysis, multi-dimensional scaling method, and so forth are often used, many other dimension reduction techniques have been proposed. Non-Patent Document 2 explains a typical method that effectively reduces the number of dimensions.
However, upon reduction of the number of dimensions, features suitable for pattern recognition may not always be selected. Thus, methods that improve clustering performances by changing pattern similarities or dissimilarities have been proposed.
Non-Patent Document 3 describes that neighbor determination accuracies are improved by using an L1/k norm (where k is an integer equal to or greater than 2) as the distance scale in D dimensional space instead of using an L2 norm. On the other hand, Non-Patent Document 3 reports that robustness against noises are improved by using the L1/k norm.